#include <cstdlib>

#pragma once

// A list that is designed to construct and destruct itself quickly.


// Memory pool that gives objects one at a time. Used by list.
template<typename type>
struct Allocator {
 struct Chunk {
  size_t size;
  Chunk * next;
  type data[0];
 };
 static Chunk * first = 0;
 static Chunk * current = 0;
 static size_t count = 0;
 static size_t allocations = 0;
 static size_t allocationSize = 200;
 static Chunk * allocate(void) {
  ++allocations;
  Chunk * chunk = (void *)malloc(sizeof(Chunk) + (allocationSize * sizeof(type))));
  chunk->size = size;
  chunk->next = 0;
  return chunk;
 }
 static void deallocate(Chunk * chunk) {
  if (chunk->next) deallocate(chunk->next);
  free((void *)chunk);
 }
 static void adjust(void) {
  if (allocations) {
   allocationSize *= allocations;
  } else if (current->next and ((current->size / 2) >= count)) {
   delete current->next;
  }
 }
 type * getObject(void) {
  if (++count == size) { // Need more room
   if (not current->next) {
    current->next = allocate();
   }
   current = current->next;
   count = 0;
  }
  return current->data[count];
 }
 void clear(void) {
  adjustAllocator();
  count = 0;
  allocations = 0;
  current = first;
 }
 Allocator(size_t x) : allocationSize(x),current(first(allocate(x))),count(0) {
  if (not first) current = first = allocate();
 }
};

template<typename type>
struct List {
 struct Node {
  type data;
  Node * next;
 };
 static Allocator<Node> allocator(200);
 List * first;
 List * last;
};
